/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package aufgabe1;

import java.util.Random;

/**
 * 
 * @author benjamin
 */
public class BackPackFactory<T extends Item> {
	private final static int MAX_RANDOM = 200;
	private int _bestTry = 0;
	private int _allTries = 0;

	/**
	 * Generate random items
	 * 
	 * @param count
	 *            - how many items
	 * @param minSize
	 *            - minimum size of item
	 * @param maxSize
	 *            - maximum size of item
	 * @param minValue
	 *            - minimum value of item
	 * @param maxValue
	 *            - maximum value of item
	 * @return
	 */
	public Item[] generateRandomItems(int count, int minSize, int maxSize,
			int minValue, int maxValue) {
		Item[] items = new Item[count];

		Random rndSize = new Random();
		Random rndValue = new Random();

		for (int i = 0; i < count; i++) {
			int size = rndSize.nextInt(maxSize - minSize) + minSize;
			int value = rndValue.nextInt(maxValue - minValue) + minValue;
			items[i] = new Item("ItemNo. " + i, size, value);
		}
		return items;
	}

	/**
	 * Pack a backpack with the given parameters
	 * 
	 * @param type
	 *            - algorithm type
	 * @param items
	 *            - item list
	 * @param backPackSize
	 *            - size of backpack
	 * @return - best solution
	 */
	public BackPack<T> pack(PackType type, T[] items, int backPackSize) {
		BackPack<T> rv = null;
		resetCounter();
		switch (type) {
		case BACKTRACKING:
			rv = createWithBacktracking(items, backPackSize);
			break;
		case BACKTRACKING_H1:
			rv = createWithBacktrackingH1(items, backPackSize);
			break;
		case RANDOM:
			rv = createWithRandom(items, backPackSize);
			break;
		}
		return rv;
	}

	/**
	 * Pack in a random order
	 * 
	 * @param items
	 * @param backPackSize
	 * @return - best result of MAX_RANDOM times
	 */
	private BackPack<T> createWithRandom(Item[] items, int backPackSize) {
		BackPack<T> best = new BackPack<T>("random", backPackSize);

		/*
		 * generate MAX_RANDOM backpack's
		 */
		for (int i = 0; i < MAX_RANDOM; i++) {
			BackPack<T> curr = new BackPack<T>("random", backPackSize);
			boolean[] picked = new boolean[items.length];
			boolean full = false;
			int pickCounter = 0;
			int pick;
			Random r = new Random();

			/*
			 * pack BackPack - while items are available and backpack is not
			 * full
			 */
			while ((pickCounter < items.length) && (!full)) {
				/*
				 * generate a new random number, if a item is already picked a
				 * new number will be generated
				 */
				do {
					pick = r.nextInt(items.length);
				} while (picked[pick]);

				/*
				 * Pick item and pack it
				 */
				picked[pick] = true;
				T item = (T) items[pick];

				if (item.getSize() <= curr.freeSpace()) {
					/*
					 * BackPack has enough free space
					 */
					curr.pack(item);
				} else {
					/*
					 * BackPack is full
					 */
					full = true;
				}
			}

			/*
			 * Set best BackPack
			 */
			if (curr.contentValue() > best.contentValue()) {
				best = curr;
				_bestTry = i;
			}
		}
		_allTries = MAX_RANDOM;

		return best;
	}

	/**
	 * Create a backtrack with the backtracking algorithm
	 * 
	 * @param items
	 *            - item list
	 * @param backPackSize
	 * @return - best backtrack
	 */
	private BackPack<T> createWithBacktracking(Item[] items, int backPackSize) {
		BackPack<T> backPack = new BackPack<T>("backtracking", backPackSize);
		BackPack<T> best = backPack.clone();

		return backtracking(items, 0, backPack, best, items.length);
	}

	/**
	 * Reset all perfomance data
	 */
	private void resetCounter() {
		_allTries = 0;
		_bestTry = 0;
	}

	/**
	 * Backtracking algorithm
	 * 
	 * @param items
	 *            - item list
	 * @param index
	 *            - working index
	 * @param backPack
	 *            - current backPack
	 * @param best
	 *            - best backPack
	 * @param length
	 *            - size of items
	 * @return - best solution
	 */
	private BackPack<T> backtracking(Item[] items, int index,
			BackPack<T> backPack, BackPack<T> best, int length) {
		/*
		 * Stop recursion
		 */
		if ((index == length) || (backPack.freeSpace() == 0)) {
			_allTries++;
			if (backPack.contentValue() > best.contentValue()) {
				_bestTry = _allTries;
				return backPack.clone();
			}
			return best;
		}

		/*
		 * Iterate through items
		 */
		for (int i = index; i < length; i++) {

			if (items[i].getSize() <= backPack.freeSpace()) {
				/*
				 * Item fit's --> pack to backpack
				 */
				backPack.pack((T) items[i]);
				// picked[i] = true;
				/*
				 * new recursive call
				 */
				best = backtracking(items, (i + 1), backPack, best, length);

				/*
				 * one step back
				 */
				// picked[i] = false;
				try {
					backPack.unpack();
				} catch (BackPackException ex) {
				}
			}
		}

		_allTries++;
		if (backPack.contentValue() > best.contentValue()) {
			_bestTry = _allTries;
			return backPack.clone();
		}
		return best;
	}

	/**
	 * Return all perfomance data
	 * 
	 * @return
	 */
	public String getPerfData() {
		return "All tries: " + _allTries + ", Best try: " + _bestTry;
	}

	/**
	 * Create a backpack with the backtracking algorithm and heuristic
	 * 
	 * @param items
	 * @param backPackSize
	 * @return - best backpack
	 */
	private BackPack<T> createWithBacktrackingH1(Item[] items, int backPackSize) {
		BackPack<T> backPack = new BackPack<T>("backtracking h1", backPackSize);
		BackPack<T> best = backPack.clone();

		int stop = items.length;
		int tmpSize = 0;

		/*
		 * Sort items: best value/size relation first
		 */
		for (int j = 0; j < stop; j++) {
			for (int i = (j + 1); i < items.length; i++) {
				if (items[i].getSize() <= backPackSize) {
					if ((items[j].getValue() / items[j].getSize()) < (items[i]
							.getValue() / items[i].getSize())) {
						Item tmp = items[j];
						items[j] = items[i];
						items[i] = tmp;
					}
				} else {
					/*
					 * move item which is bigger then backpack self to back
					 */
					Item tmp = items[j];
					items[j] = items[i];
					items[i] = tmp;
				}
			}
			/*
			 * if the first sorted elements have more than 1.5 size of backpack,
			 * stop sorting.
			 */
			tmpSize += items[j].getSize();
			if (tmpSize > (backPackSize * 1.5)) {
				stop = j;
			}
			j++;
		}

		return backtracking(items, 0, backPack, best, stop);
	}

}